// 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

// 示例 1:

// 输入: [3,2,1,5,6,4] 和 k = 2
// 输出: 5
// 示例 2:

// 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
// 输出: 4
// 说明:

// 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

#include "../stdc++.h"

using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > q{}; // 小根堆
        for (int& num : nums) {
            q.push(num);
            if (q.size() > k) {
                q.pop();
            }
        }
        return q.top();
    }
};

// 重复的元素也计算个数
// 不考虑传入的数组是否被改变
// 冒泡排序，冒k个泡即可
// O(n)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i{0}; i < k; ++i) {
            int max_index{i};
            for (int j{i}; j < n; ++j) {
                if (nums[j] > nums[max_index]) max_index = j;
            }
            swap(nums[i], nums[max_index]);
        }
        return nums[k-1];
    }
};

// 随机快排
// O(n)
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0)); // 用当前时间来设定rand函数所用的随机数产生算法的种子值
        int n = nums.size();
        return quickSelect(nums, 0, n - 1, n - k);
    }
    int quickSelect(vector<int>& nums, int l, int r, int index) {
        int q = randomPartition(nums, l, r);
        if (q == index) return nums[q];
        else return q < index ? quickSelect(nums, q + 1, r, index) : quickSelect(nums, l, q - 1, index);
    }
    int randomPartition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(nums[i], nums[r]);
        return partition(nums, l, r);
    }
    // 返回pivot，pivot左边的比右边的小
    int partition(vector<int>& nums, int l, int r) {
        int x = nums[r];
        int i = l - 1;
        for (int j = l; j < r; ++j) {
            if (nums[j] <= x) swap(nums[++i], nums[j]);
        }
        swap(nums[i+1], nums[r]);
        return i + 1;
    }
};

// 普通快排
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        quickSort(nums, 0, n - 1); // 从小到大排序
        return nums[n - k];
    }
    void quickSort(vector<int>& nums, int l, int r) {
        if (l > r) return;
        int i{l};
        int j{r};
        int v = nums[l];
        while (i < j) {
            while (nums[j] >= v && i < j) --j;
            while (nums[i] <= v && i < j) ++i;
            if (i < j) swap(nums[i], nums[j]);
        }
        swap(nums[l], nums[i]);
        quickSort(nums, l, i - 1);
        quickSort(nums, i + 1, r);
    }
};

// 堆排序
// 大根堆，建堆，调整，删除
// arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        int n = nums.size();
        for (int i = n - 1; i >= n - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
    // 建堆
    void buildMaxHeap(vector<int>& nums, int heapSize) {
        // 从最后一个非叶子结点开始，叶结点自然不用调整，第一个非叶子结点 arr.length/2-1
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(nums, i, heapSize);
        }
    }
    // 调整
    void maxHeapify(vector<int>& nums, int i, int heapSize) {
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        int max = i;
        if (l < heapSize && nums[l] > nums[max]) max = l;
        if (r < heapSize && nums[r] > nums[max]) max = r;
        if (max != i) {
            swap(nums[i], nums[max]);
            maxHeapify(nums, max, heapSize);
        }
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int heapSize{n};
        buildMaxHeap(nums, heapSize);
        for (int i{n - 1}; i >= n - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
private:
    void buildMaxHeap(vector<int>& nums, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(nums, i, heapSize);
        }
    }
    void maxHeapify(vector<int>& nums, int i, int heapSize) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int maxIndex{i};
        if (left < heapSize && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if (right < heapSize && nums[right] > nums[maxIndex]) {
            maxIndex = right;
        }
        if (maxIndex != i) {
            swap(nums[i], nums[maxIndex]);
            maxHeapify(nums, maxIndex, heapSize);
        }
    }
};